package leetcode.interview;
/*
数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

示例 1：

输入：[1,2,5,9,5,9,5,5,5]
输出：5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-majority-element-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
使用摩尔投票法得出众数
然后检查该数是否过半
 */
public class Test1710 {
    public int majorityElement(int[] nums) {
        int vote=0,major=0;
        if(nums.length==1)
            return nums[0];
        major=nums[0];

        for(int i=0;i<nums.length;i++){
            if(vote==0){
                major=nums[i];
            }
            if(major==nums[i]){
                ++vote;
            }
            else if(major!=nums[i]){
                --vote;
            }
        }

        vote=0;

        for(int i=0;i<nums.length;i++){
            if(major==nums[i])
                ++vote;
            if(vote>nums.length/2)
                return major;
        }

        return -1;
    }
}
